// https://leetcode-cn.com/problems/target-sum/
// 494. Target Sum
export function findTargetSumWays(nums: number[], target: number): number {
    const sum = nums.reduce((a, b) => a + b);
    if (sum < target || (sum - target) & 1) return 0;

    const neg = (sum - target) / 2;
    const dp = new Array(neg + 1).fill(0);
    dp[0] = 1;
    for (let num of nums) {
        for (let j = neg; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }

    return dp[neg];
}
